题意
给出一棵无根树和树上的若干条链
求无序点对数，使得这两个点不重合且它们之间的路径至少被一条链包含
题解
特别暴力的做法，对于每个节点开一棵权值线段树，统计权值不为0的个数
对于一条链，分别在$u$，$v$，$f_{lca(u,v)}$打1,1,-2标记，自底向上线段树合并即可
线段树动态开点+标记永久化，因为每个区间如果被加上一定会被减去
调试记录
线段树中当前节点的区间若被操作区间覆盖，修改Min时也要修改tg
-2要打在lca的父亲上1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
using namespace std;
const int maxn = 1e5 + 5;
struct E{
int to, nxt;
}e[maxn << 1];
int head[maxn], tot = 0;
void addedge(int u, int v){
e[++tot].to = v, e[tot].nxt = head[u];
head[u] = tot;
}
struct T{
struct A{
int l, r, Min, tg, ls, rs;
}a[maxn * 400];
int rt[maxn];
void upd(int cur, int l, int r, int k){
if (a[cur].l > r || a[cur].r < l) return;
if (a[cur].l >= l && a[cur].r <= r){
a[cur].Min += k;
a[cur].tg = (a[cur].Min > 0) ? a[cur].r - a[cur].l + 1 : LS.tg + RS.tg;
return;
} int M = a[cur].l + a[cur].r >> 1;
if (!a[cur].ls && M >= l){
a[++tot].l = a[cur].l; a[tot].r = M;
a[cur].ls = tot;
}
if (!a[cur].rs && M < r){
a[++tot].l = M + 1; a[tot].r = a[cur].r;
a[cur].rs = tot;
}
if (a[cur].ls) upd(a[cur].ls, l, r, k);
if (a[cur].rs) upd(a[cur].rs, l, r, k);
a[cur].tg = (a[cur].Min > 0) ? a[cur].r - a[cur].l + 1 : LS.tg + RS.tg;
}
int Merge(int cur, int v){
if (!cur) return v;
if (!v) return cur;
a[cur].Min += a[v].Min;
if (a[cur].l != a[cur].r)
a[cur].ls = Merge(a[cur].ls, a[v].ls),
a[cur].rs = Merge(a[cur].rs, a[v].rs);
a[cur].tg = (a[cur].Min > 0) ? a[cur].r - a[cur].l + 1 : LS.tg + RS.tg;
return cur;
}
}t;
int dep[maxn], f[maxn], sz[maxn], son[maxn];
void dfs1(int cur, int fa){
dep[cur] = dep[fa] + 1; f[cur] = fa; sz[cur] = 1;
for (int i = head[cur]; i; i = e[i].nxt){
int v = e[i].to;
if (v != fa){
dfs1(v, cur);
if (sz[v] > sz[son[cur]]) son[cur] = v;
sz[cur] += sz[v];
}
}
}
int id[maxn], tdx = 0, top[maxn];
void dfs2(int cur, int topf){
top[cur] = topf; id[cur] = ++tdx;
if (!son[cur]) return;
dfs2(son[cur], topf);
for (int i = head[cur]; i; i = e[i].nxt)
if (e[i].to != f[cur] && e[i].to != son[cur]) dfs2(e[i].to, e[i].to);
} LL ans = 0;
struct U{
int l, r, k;
U(int a = 0, int b = 0, int c = 0){
l = a; r = b; k = c;
}
}; vector <U> vec[maxn];
int n, Q;
void dfs(int cur, int fa){
for (int i = head[cur]; i; i = e[i].nxt){
int v = e[i].to;
if (v == fa) continue;
dfs(v, cur); t.rt[cur] = t.Merge(t.rt[cur], t.rt[v]);
}
for (int j = 0; j < vec[cur].size(); j++){
t.upd(t.rt[cur], vec[cur][j].l, vec[cur][j].r, vec[cur][j].k);
// printf("::%d %d %d\n", vec[cur][j].l, vec[cur][j].r, vec[cur][j].k);
}
// if (cur == 5) printf("%d\n", t.a[t.rt[cur]].tg);
ans += t.a[t.rt[cur]].tg;
}
vector <U> tmp;
int split(int u, int v){
tmp.clear();
while (top[u] != top[v]){
if (dep[top[u]] > dep[top[v]]) swap(u, v);
tmp.push_back((U){id[top[v]], id[v], 0});
v = f[top[v]];
}
if (dep[u] > dep[v]) swap(u, v);
tmp.push_back((U){id[u], id[v], 0});
return u;
}
int main(){
scanf("%d%d", &n, &Q);
for (int u, v, i = 1; i < n; i++){
scanf("%d%d", &u, &v);
addedge(u, v); addedge(v, u);
} dfs1(1, 0); dfs2(1, 1);
for (int i = 1; i <= n; i++){
t.rt[i] = i, t.a[i].l = 1, t.a[i].r = n;
vec[i].push_back((U){id[i], id[i], 1});
vec[f[i]].push_back((U){id[i], id[i], -1});
} tot = n;
for (int u, v, i = 1; i <= Q; i++){
scanf("%d%d", &u, &v);
int t = split(u, v);
for (int j = 0; j < tmp.size(); j++){
vec[u].push_back((U){tmp[j].l, tmp[j].r, 1});
vec[v].push_back((U){tmp[j].l, tmp[j].r, 1});
vec[f[t]].push_back((U){tmp[j].l, tmp[j].r, -2});
// printf("::%d %d\n", tmp[j].l, tmp[j].r);
}
}
dfs(1, 0); printf("%lld\n", (ans - n) >> 1);
return 0;
}